Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Herzlich willkommen in die Filmreihen, sozusagen in die Kamerareien, die sich später angucken.

Wir sind gestern mitten drin stehen geblieben bei den Winkors Flow-Algorithmen und haben uns da

erstmal die grundlegenden Sachen angeguckt, Optimalitätskriterien sind wir dabei und haben das erste

kennengelernt, nämlich zu sagen, ein Fluss ist dann minimal, wenn keine negativen Kreise in diesem

Residualgrafen auftreten. Das ist genau so was, wie wir auch schon vorher bei Max Flow hatten, also

ein Fluss ist dann maximal, wenn es keinen augmentierten Weg gibt. Haben wir hier gesagt,

wenn es keine sozusagen negative Kreise in dem Residualgrafen gibt, was letztendlich ja auch

augmentierende Kreise sind. Also wenn ich in meinem Residualgrafen einen gerichteten Kreis mir suche,

der entspricht ja sozusagen in dem Ausgangsgrafen einem augmentierten Kreis, wenn man so möchte.

Also eigentlich sehr analoges Konzept zu dem, was wir bei Max Flow hatten. Wir haben ja auch

gesehen bei der Definition vom Winkors Flow-Problem, es sind ja zwei Randbedingungen,

einmal die Kapazitätsbedingungen, einmal die Flusserhaltungsbedingungen, wobei wir jetzt eben

sagen, vorher bei Max Flow hat man gesagt, alles was reinfließt, wie das was rausfließt, ist gleich

Null. Jetzt geben wir dort einen gewissen Wert vor an dem Knoten B von V und das ist das einzige,

was wir fordern, dass die Summe der BVs gleich Null ist. Das heißt, die Bedarfe und die Anfragen

sozusagen müssen balanciert sein, sagt man auch. So und damit haben wir gesehen, dass man auch

jedes beliebige Max Flow als auch Kürzeste-Wege-Problem als ein solches Winkors Flow-Problem lesen,

modellieren können und damit, wenn man Algorithmen dafür haben, damit auch automatisch für die

anderen, wobei wir ja heute sehen werden, dass wir die Basisalgorithmen, die wir bislang

kennengelernt haben, brauchen, um hier eben Winkors Flow-Probleme auch lösen zu können.

So und wir sind gestern stehen geblieben, wir hatten dieses negative Kreiskriterium kennengelernt

und wir hatten jetzt noch, waren uns dabei, ein zweites Kriterium nämlich zu erarbeiten,

aufgrund sogenannter Knotenpotenziale, so haben wir das genannt, was aber im Wesentlichen auch

diesem Aspekt der, wie wir bei Kürzesten-Wege schon kennengelernt haben, dann nicht die Werte

oder die Distanzwerte sozusagen von einem bestimmten Knoten s aus, aber wenn wir sehen,

dass da eine sehr, sehr starke Ähnlichkeit, wir haben schon eine Definition gesehen, aber die

werden wir dann auch im Algorithmus noch kennenlernen, dass da eine starke Korrelation

zu den Labels von Kürzesten-Wegen nachher sein wird. Gibt es bis dahin noch Fragen zu gestern?

Gut, wenn das nicht der Fall ist, also noch mal zur Erinnerung, wir hatten Knotenpotenziale

definiert, vielleicht sage ich das nochmal, schreihe ich das nochmal kurz hin, wir hatten so eine

Funktion Pi von V nach R, die haben wir einfach Potenzial genannt und wir hatten dann Gewichte

eingeführt, dIj Pi, die waren die alten, die Originalgewichte plus Pi, Pi von I minus Pi von J,

das waren die reduzierten Bogen oder die reduzierten Kosten von Bogen Ij. Also ich hatte ja schon

erinnert, dass, also wir hatten ja praktisch H genau das Gleiche bei Kürzesten-Wegen, wir werden

später sehen, wenn wir uns mit linearen Programmen beschäftigen, das was hier steht, entspricht

genau den reduzierten Kosten, die in linearen Programmen auftreten, wo wir uns die Dinge dann

angucken werden, in einem deutlich allgemeineren Kontext, wo wir sehen, wenn man sich diesen

Spezialfallweg oder Spezialfallfluss anschaut, dass dann genau diese Bedingungen hier stehen,

das vielleicht nur schon mal als Hinweis, ich werde dann, das wird aber dann vermutlich nach

Weihnachten sein, genau nochmal auf diesen Punkt hinweisen. So und jetzt das optimalitätsgithäum,

das zweite, das fassen wir zusammen in einem Satz, das ist der Satz 9,4, also sei x ein zulässiger

Fluss, das x ist optimal, genau dann, wenn es existiert so ein Knotenpotential Pi, mit der

Eigenschaft, dass diese W ij, Pis alle größer gleich Null sind für alle ij aus A von x.

Also nochmal zur Erinnerung, bei Kürzesten-Wegen haben wir genau das selbe, da stand halt dann

die d ij sozusagen größer gleich Null oder bei Max Flow hat man das ja auch ganz ähnlich

schon, also dieses Githäum hier taucht da immer wieder auf. So, wir wollen mal das beweisen

und wir beweisen das, indem wir es auf den anderen Satz zurückführen, also wir hatten

ja schon gesagt, x ist optimal, genau dann, wenn es keine negativen Kreise in dem Residualgrafen

gibt, bezüglich, also Entschuldigung, da muss ich das quer drüber machen, also wir hatten